package com.mccken.practice.data_structure.data_06;

import java.util.Random;

import com.mccken.practice.top100.Top_1$20.Top_13.Temp_13;

/**
 * 不用记录当前链表中有多少层级了，直接弄一个值来限制最高层级即可，管他有多少层呢
 * 
 * 
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-06 20:13
 **/
public class SkipList implements ISkipList{
	
	// 节点数量
	public int num;
	
	// 最高层级数
	public int max_height;
	
	// 虚拟头节点、尾结点                 
	public SkipNode head;
	public SkipNode tail;
	
	// 概率随机
	private Random random;
	
	public SkipList(){
		this.num = 0;
		// 设置最高层数为 6 层
		this.max_height = 6;
		this.random = new Random();
		
		this.head = new SkipNode(Integer.MIN_VALUE, null);
		this.tail = new SkipNode(Integer.MAX_VALUE, null);
		// 链表头尾关联
		this.head.right = tail;
		this.tail.left = head;
	}
	
	// 查找, 根据指定分数查找数据
	private SkipNode find(Integer score) {
		SkipNode start = this.head;
		while (true) {
		
			// 往右寻找，找到比score小的最大节点
			while (start.right.score <= score) {
				start = start.right;
			}
		
			// 走到这里，在这一层右边节点比查询大，就向下定位
			if (start.down != null) {   // 如果下一层不为null，则继续定位，继续循环，使得下一层，继续往右
				start = start.down;
			} else {    // 如果下一层是null，不再循环，将节点返回出去
				break;
			}
		}

		/**
		 * 这里的start.score <= score
		 * 分两种情况：
		 * 1. 如果查找的分数存在，则返回该对象的底层节点
		 * 2. 如果查找的分数不存在，则返回接近该对象的底层节点
		 */
		return start;
	}
	
	
	@Override
	public Object get(Integer score) {
		if (num < 1) {
			return null;
		}
		SkipNode mark = find(score);
		if (mark.score.equals(score)) {
			return mark.value;
		}else {
			return null;
		}
	}

	@Override
	public void put(Integer score, Temp_13 value) {
		// 寻找对应分数，如果不存在，则返回最近位置的分值，等于已经找到了合适的插入位置
		SkipNode mark = find(score);
		
		// 如果找到的节点分值 == score，则表示已经存在，直接更新
		if (mark.score.equals(score)) {
			mark.value = value;
			return;
		}
		
		// 否则进行插入
		SkipNode newNode = new SkipNode(score, value);
		/*
		    将节点插入到最底层的链表中
		 */
		newNode.left = mark;
		newNode.right = mark.right;
		mark.left.left = newNode;
		mark.right = newNode;
		
		/*
			计算垂直方向的链表
		 */
		int i = 0;
		while (random.nextDouble() < 0.5) {
			if (i>max_height) {
				break;
			}
		
			// 往左找有上层链表的节点
			while (mark.up == null) {
				mark = mark.left;
			}
		
			mark = mark.up;
			
			SkipNode upNewNode = new SkipNode(score, null);
			upNewNode.left = mark;
			upNewNode.right = mark.right;
			mark.right.left = upNewNode;
			mark.right = upNewNode;
			
			upNewNode.down = newNode;
			newNode.up = upNewNode;
		
			// 将当前引用指向新创建的上层引用,然后继续下一个while循环，相当于再用随机数计算下一个level
			newNode = upNewNode;
			i++;
		}
		// 底层节点数
		++num;
	}

	/**
	 * 只需要断开左右就行了， 上下直接不用管~等着JVM回收
	 */
	@Override
	public boolean remove(Integer score) {
		SkipNode mark = find(score);
		
		if (!mark.score.equals(score)) {
			return true;
		}
		
		SkipNode del;
		while (mark != null) {
			del = mark.up;
			mark.left.right = mark.right;
			mark.right.left = mark.left;
		
			mark = del;
		}
		
		// 底层节点数
		num--;
		return true;
	}
}
